home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c-part2 / 11314 < prev    next >
Encoding:
Internet Message Format  |  1996-08-05  |  3.7 KB
  1. Path: netaxs.com!not-for-mail
  2. From: grulm@netaxs.com (J. A. McNamara)
  3. Newsgroups: comp.lang.c
  4. Subject: Re: binary tree question
  5. Date: 23 Mar 1996 02:59:59 GMT
  6. Organization: Philadelphia's Complete Internet Provider
  7. Message-ID: <4ivpff$a6j@netaxs.com>
  8. References: <4isglj$cgg@netaxs.com> <4iumkjINNsp3@keats.ugrad.cs.ubc.ca>
  9. NNTP-Posting-Host: unix5.netaxs.com
  10. X-Newsreader: TIN [UNIX 1.3 950824BETA PL0]
  11.  
  12. Kazimir Kylheku (c2a192@ugrad.cs.ubc.ca) wrote:
  13. : In article <4isglj$cgg@netaxs.com>, J. A. McNamara <grulm@netaxs.com> wrote:
  14.  
  15. :  > /* blah blah blah I wanna free the tree */
  16. :  >
  17. :  >link *inorder(tree_n *tn, link *tail, int *i)   /* read tree into list */
  18. :  >    {
  19. :  >        if (tn != NULL) {
  20. :  >            tail = inorder(tn->l, tail, i);
  21. :  >            tail = addlink(tail, tn->f);      /* hand data ptr to list */
  22. :  >            (*i)++;                           /* keep track of total   */
  23. :  >            tail = inorder(tn->r, tail, i);
  24. :  >        }
  25. :  >        if (tn!=NULL) free(tn); tn=NULL;
  26. :  >        return tail;
  27. :  >    }
  28.  
  29. : This is not a pure ``inorder'' traversal. The nodes are being added to the
  30. : linked list in order, but you are freeing in post-order (children are visited
  31. : first, then you free the parent).
  32.  
  33. hmmm, yeah, I see yr point.  would that affect anything?  I think I did it
  34. that way originally because I was freeing the children, so I wanted it in
  35. a safe place.
  36.  
  37. : Why don't you combine the two if() statements into one? They have precisely the
  38. : same expression, and tn is never assigned to in the body of the first one, so
  39. : the evaluation of the expression doesn't change.
  40. : You do not need to assign NULL to the ``tn'' pointer after you have invoked
  41. : free() on it. This is a waste of time, since it has been passed to the
  42. : procedure by value. You are only affecting the value of the function parameter
  43. : ``tn'', not any external object. This value is never used, so the compiler will
  44. : throw that assignment away at the optimization phase.
  45.  
  46. heh heh heh . . .  I noticed these two issues while posting; I didn't 
  47. change the code because I *knew* it compiled and worked this way.  this is
  48. what happens when an inexperienced programmer writes > 400 lines of code
  49. in like four days.  let this be a warning to all.  the program actually 
  50. does work, oddly enough.
  51.  
  52. :  >free(tn->l); tn->l=NULL;
  53. :  >free(tn->r); tn->r=NULL;
  54. :  >
  55. :  >. . .  which gave me some serious garbage, though I'm not quite sure why.
  56.  
  57. : Because you probably did not check whether the children are null pointers or
  58. : not, only whether tn is a null pointer. Just because tn is a valid tree node
  59. : doesn't mean that tn->l or tn->r are.
  60.  
  61. jesus, I'm really batting 1000 here.  I don't grok why that would give the 
  62. list pointers to garbage, though; that stuff was postorder, just like the
  63. free() in the whole function I posted.  ??
  64.  
  65. : The above modification will also fail to
  66. : free the root node.
  67.  
  68. ah!  small potatoes, but worth noting.
  69.  
  70. : Your code appears fine. That it's not actually freeing memory is not
  71. : surprising. Many free() implementations don't free memory, they only return
  72. : free blocks to a list from where subsequent malloc() invocations can obtain
  73. : memory quickly.
  74.  
  75. how isn't that freeing?  if this'll clarify things any, I want to free the 
  76. tree to make room for the list, so one shrinks as the other grows.  I'd
  77. guess (!) that the malloc() in the addlink() function would then pull 
  78. memory off that list, right?   (and both structs are the same size, three 
  79. pointers).  does it then not free the memory for *non*-malloc() purposes?
  80. Or only sorta free it?  This is something I'm kinda foggy about in 
  81. general.
  82.  
  83.  
  84. -- 
  85.                           j a mcnamara  aramancm a j
  86.                       grulm@netaxs.com  moc.sxaten@mlurg
  87.